#递归法解决问题，自顶向下计算，时间复杂度高.T(n)=O(n^2)
def fun(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fun(n-1) + fun(n-2)

n = int(input())
num = fun(n)
print(num)

#递归中存在重复问题，将已经计算过的值保存到字典。T(n) = O(n)
di = {}
def func(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        if n in di:
            return di.get(n)
        else:
            esult = func(n-1) + func(n-2)
            di[n] = esult
            return esult
n = int(input())
num = func(n)
print(num)

#循环方式，自底向上累加，用变量临时保存子问题的解.T(n) = O(n)
def fibonacci(n):
    a = 0
    b = 1
    if n == 0:
        return 0
    elif n == 1:
        return 1
    for i in range(1,n):
        c = a + b
        a = b
        b = c
    return b
n = int(input())
num = fibonacci(n)
print(num)




